﻿
namespace Leetcode.N2030;

public class Solution
{
    public string SmallestSubsequence(string s, int k, char letter, int repetition)
    {
        // 需要指定字符的数量
        var needSpecifyLettesCount = repetition;

        // 剩余指定字符的数量
        var remainSpecifyLettesCount = s.Count(i => i == letter);

        var stack = new Stack<char>();

        for (int i = 0; i < s.Length; i++)
        {
            // 需要的字符数量
            var needLettersCount = k - stack.Count();

            // 剩余的字符数量
            var remainLettersCount = s.Length - i - 1;

            // 剩余数量不够时，剩余的字符都需要加入栈中
            if (remainLettersCount < needLettersCount)
            {
                stack.Push(s[i]);
                continue;
            }

            if (s[i] == letter)
            {
                // 如果是指定的字符，剩余字符减少一个
                remainSpecifyLettesCount--;
            }

            while (stack.Count > 0 && stack.Peek() > s[i])
            {
                var pop = stack.Peek();
                needLettersCount = k - stack.Count();
                // 剩余字符不够了，无需出栈
                if (remainLettersCount < needLettersCount)
                {
                    break;
                }
                else if (pop == letter)
                {
                    // 指定的字符不够时，无需出栈
                    if (remainSpecifyLettesCount <= needSpecifyLettesCount)
                    {
                        break;
                    }
                    else
                    {
                        // 指定字符出栈后，需要指定字符加1
                        needSpecifyLettesCount++;
                    }
                }
                stack.Pop();
            }

            if ((s[i] == letter && stack.Count < k) || stack.Count < k - (needSpecifyLettesCount >= 0 ? needSpecifyLettesCount : 0))
            {
                stack.Push(s[i]);
                if (s[i] == letter)
                {
                    // 指定字符入栈后，需要指定字符减1
                    needSpecifyLettesCount--;
                }
            }

        }
        return new string(stack.Reverse().ToArray());
    }
}